1. Field of the Invention
The present invention relates to managing memory within a computer system. More specifically, the present invention relates to a method and an apparatus for performing generational garbage collection in a segmented heap.
2. Related Art
Modem object-oriented programming systems typically allocate objects from a region of memory known as the “heap”. When an object becomes unreachable because all references to the object have been removed, the object can no longer be used. However, the object continues to occupy memory space within the heap. At a later time, a “garbage collection” process reclaims this unused memory and makes it available to accommodate other objects. This garbage collection process may additionally perform compaction by rearranging objects in the heap to reduce memory fragmentation.
One of the most efficient types of garbage collectors is a “generational garbage collector”. In a generational garbage collector, new objects are allocated in a “young generation” area of the heap. If an object continues to have references over a specified number of garbage collections cycles, the object is promoted to one or more old generation areas of the heap. A generational garbage collector performs garbage collection frequently on the young generation area of the heap, while performing garbage collection less frequently on old generation areas. This tries to match typical program behavior where most newly created objects are short-lived, and are thus reclaimed during garbage collection of the young generation. Long-lived objects in the old generation areas tend to persist in memory. Hence, the old generation areas need to be garbage collected less frequently. This greatly reduces the effort involved in garbage collection because only the young generation area of the heap needs to be garbage collected frequently.
FIG. 1 illustrates a young generation area 102 and an old generation area 104 within a heap. As is described above, a new object is initially allocated in young generation area 102. After a specified number of garbage collection cycles, if the object is still referenced, the object is promoted to old generation area 104. Old generation area 104 typically comprises a large contiguous area of memory that is divided into “cards”. Each card contains a fixed amount of memory, such as 29 bytes. Note that an object 114 within old generation area 104 can have a pointer an object 112 in young generation area 102.
When the system garbage collects young generation area 102, references from old generation area 104 to objects in young generation area 102 need to be located. To make locating these references easier, the system maintains a card table 106 that is associated with old generation area 104. When a pointer in old generation area 104 is updated, a corresponding entry in the card table 106 is marked. For example, FIG. 1 shows marked entry 110 in card table 106, which indicates that a pointer to an object in a corresponding card 108 has been updated. During garbage collection, only marked cards need to be examined for current references to objects in young generation area 102. This eliminates the need to scan through references in all of the old generation area 104, which can significantly improve performance of the garbage collection process.
The above-described method of garbage collection works well for an old generation area that is allocated in contiguous memory. A problem exists, however, in using this type of garbage collection technique in small, embedded systems do not support virtual memory. In this type of system, it is not practical to maintain a contiguous heap, which can be grown and shrunk depending on the dynamically changing requirements of applications running on these small systems.
What is needed is a method and an apparatus that provides the advantages of using card tables as described above without having to maintain a large contiguous heap.